package com.learn.algorithm;

import java.util.HashSet;

/**
 * 位图就是用bit组成的数组来存放值, 用bit 1代表存在 bit 0代表不存在
 * 取值和存值都使用位运算 限制是必须是连续范围且不能过大
 * 好处是极大节省空间因为一个数字只占用1bit空间
 */
public class Bitmap {
    private int[] set;

    public Bitmap(int n) {
        this.set = new int[n / 32 + 1];
    }

    public void add(int num) {
        this.set[num / 32] |= 1 << (num % 32);
    }

    public void remove(int num) {
        this.set[num / 32] &= ~(1 << (num % 32));
    }

    public void reverse(int num) {
        this.set[num / 32] ^= (1 << (num % 32));
    }

    public boolean contains(int num) {
        return ((this.set[num / 32] >> (num % 32)) & 1) == 1;
    }

    public static void main(String[] args) {
        int n = 1000;
        int times = 10000;
        Bitmap bitmap = new Bitmap(n);
        HashSet<Integer> set = new HashSet<>();

        for (int i = 0; i < times; i++) {
            double decide = Math.random();
            int number = (int) (Math.random() * n);
            if (decide < 0.333) {
                bitmap.add(number);
                set.add(number);
            } else if (decide < 0.666) {
                bitmap.remove(number);
                set.remove(number);
            } else {
                bitmap.reverse(number);
                if (set.contains(number)) {
                    set.remove(number);
                } else {
                    set.add(number);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (bitmap.contains(i) != set.contains(i)) {
                System.out.println("出错");
                break;
            }
        }

    }
}
